﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0097_CoinChange : IAlgorithm
    {
        // 322. 零钱兑换

        // 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
        // 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
        // 你可以认为每种硬币的数量是无限的。

        // 提示：
        //  1 <= coins.length <= 12
        //  1 <= coins[i] <= 2^31 - 1
        //  0 <= amount <= 10^4

        public void Test()
        {
            // 算法参数定义
            var coins = new int[] { 186, 419, 83, 408 };
            var amount = 6249;
            // 算法执行与打印
            Console.WriteLine(CoinChange(coins, amount));
        }

        // 算法
        public int CoinChange(int[] coins, int amount)
        {
            return CoinChange(coins, amount, new int[amount]);
        }
        private int CoinChange(int[] coins, int amount, int[] count)
        {
            if (amount < 0)
                return -1;
            if (amount == 0)
                return 0;
            if (count[amount - 1] != 0)
                return count[amount - 1];
            int min = int.MaxValue;
            foreach (var coin in coins)
            {
                int res = CoinChange(coins, amount - coin, count);
                if (res >= 0 && res < min)
                    min = 1 + res;
            }
            count[amount - 1] = (min == int.MaxValue) ? -1 : min;
            return count[amount - 1];
        }

        public int CoinChange1(int[] coins, int amount)
        {
            int max = amount + 1;
            int[] dp = new int[amount + 1];
            Array.Fill(dp, max);
            dp[0] = 0;
            for (int i = 1; i <= amount; i++)
                for (int j = 0; j < coins.Length; j++)
                    if (coins[j] <= i)
                        dp[i] = Math.Min(dp[i], dp[i - coins[j]] + 1);
            return dp[amount] > amount ? -1 : dp[amount];
        }
    }
}
